package io.github.consoles.dsa;

/**
 * Created by yiihua-013 on 17/3/31.
 * <p>
 * 一个以栈为目标的队列
 *
 * 同时支持FIFO和LIFO
 */
public class LinkedSteque<Item> {

    private class Node {
        Item item;
        Node next;
        Node prev;

        Node(Item item) {
            this.item = item;
        }
    }

    private Node first, last;

    public void push(Item item) {

        Node node = new Node(item);

        if (first == null) {
            first = last = node;
        } else {
            node.prev = last;
            last.next = node;
            last = node;
        }
    }

    public Item pop() {

        Node node = last;
        last = last.prev;
        return node.item;
    }

    public boolean isEmpty(){
        return first == null && last == null;
    }

    public void enqueue(Item item) {

        if (first == null) push(item);
        else {
            Node node = new Node(item);
            node.next = first;
            first.prev = node;
            first = node;
        }
    }

    public LinkedSteque<Item> catenation(LinkedSteque<Item> linkedSteque) {
        this.last.next = linkedSteque.first;
        linkedSteque.first.prev = this.last;
        this.last = linkedSteque.last;
        return this;
    }

}
